// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) definits fieldsfirst ansi space safe 
// Source File Name:   ConvexPolygon.java

package jones.rigid;

import java.awt.geom.Point2D;

// Referenced classes of package jones.rigid:
//            Polygon

public class ConvexPolygon extends Polygon
{

    public ConvexPolygon()
    {
    }

    public ConvexPolygon(double x[], double y[], int n)
    {
        super(x, y, n);
        if (!isConvex(x, y, n))
        {
            this.n = convexHull(this.x, this.y, this.n);
            calculateBounds();
        }
    }

    public void setPolygon(Polygon p)
    {
        super.setPolygon(p);
        if (p instanceof ConvexPolygon)
            return;
        if (!isConvex(((Polygon) (this))))
        {
            n = convexHull(x, y, n);
            calculateBounds();
        }
    }

    public void setPolygon(double x[], double y[], int n)
    {
        super.setPolygon(x, y, n);
        if (!isConvex(((Polygon) (this))))
        {
            this.n = convexHull(this.x, this.y, this.n);
            calculateBounds();
        }
    }

    public boolean isLeftConvex()
    {
        for (int i = 0; i < n; i++)
        {
            double crossProduct = crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x[(i + 2) % n], y[(i + 2) % n]);
            if (isRightTurn(crossProduct))
                return false;
            if (isLeftTurn(crossProduct))
                return true;
        }

        return false;
    }

    public boolean contains(double px, double py)
    {
        for (int i = 0; i < n; i++)
        {
            double x1 = y[(i + 1) % n] - y[i];
            double y1 = x[(i + 1) % n] - x[i];
            if (isLeftConvex())
                y1 = -y1;
            else
                x1 = -x1;
            double x2 = px - x[i];
            double y2 = py - y[i];
            double dotProduct = x1 * x2 + y1 * y2;
            if (dotProduct < 0.0D)
                return false;
        }

        return true;
    }

    public boolean intersects(double x1, double y1, double x2, double y2)
    {
        boolean isDone = true;
        for (int i = 0; i < n; i++)
        {
            if (!isLeftTurn(crossProduct(x1, y1, x2, y2, x[i], y[i])))
                continue;
            isDone = false;
            break;
        }

        if (isDone)
            return false;
        isDone = true;
        for (int i = 0; i < n; i++)
        {
            if (!isRightTurn(crossProduct(x1, y1, x2, y2, x[i], y[i])))
                continue;
            isDone = false;
            break;
        }

        if (isDone)
            return false;
        if (!isLeftConvex())
        {
            for (int i = 0; i < n; i++)
                if (isLeftTurn(crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x1, y1)) && isLeftTurn(crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x2, y2)))
                    return false;

        } else
        {
            for (int i = 0; i < n; i++)
                if (isRightTurn(crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x1, y1)) && isRightTurn(crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x2, y2)))
                    return false;

        }
        return true;
    }

    public boolean intersects(ConvexPolygon p)
    {
        return intersects(this, p);
    }

    public static boolean intersects(ConvexPolygon p1, ConvexPolygon p2)
    {
        if (!Polygon.intersectsBounds(((Polygon) (p1)), ((Polygon) (p2))))
            return false;
        else
            return getSeparatingEdge(p1, p2) == -1 && getSeparatingEdge(p2, p1) == -1;
    }

    public static int getSeparatingEdge(ConvexPolygon p1, ConvexPolygon p2)
    {
        boolean isLeftConvex = p1.isLeftConvex();
        int n1 = p1.getN();
        int n2 = p2.getN();
        for (int i = 0; i < n1; i++)
        {
            boolean isDone = true;
            for (int j = 0; j < n2; j++)
            {
                double crossProduct = crossProduct(p1.x[i], p1.y[i], p1.x[(i + 1) % n1], p1.y[(i + 1) % n1], p2.x[j], p2.y[j]);
                if ((!isLeftConvex || !isLeftTurn(crossProduct)) && (isLeftConvex || !isRightTurn(crossProduct)))
                    continue;
                isDone = false;
                break;
            }

            if (isDone)
                return i;
        }

        return -1;
    }

    public static boolean isConvex(double x[], double y[], int n)
    {
        if (n > x.length || n > y.length || n < 0)
            throw new ArrayIndexOutOfBoundsException("x.length= " + x.length + "y.length= " + y.length + "n = " + n);
        if (n < 4)
            return true;
        boolean isFirst = true;
        boolean isRightTurn = true;
        for (int i = 0; i < n; i++)
        {
            double crossProduct = crossProduct(x[i], y[i], x[(i + 1) % n], y[(i + 1) % n], x[(i + 2) % n], y[(i + 2) % n]);
            if (isRightTurn(crossProduct))
            {
                if (isFirst)
                {
                    isRightTurn = true;
                    isFirst = false;
                    continue;
                }
                if (!isRightTurn)
                    return false;
            }
            if (isLeftTurn(crossProduct))
                if (isFirst)
                {
                    isRightTurn = false;
                    isFirst = false;
                } else
                if (isRightTurn)
                    return false;
        }

        return true;
    }

    public static boolean isConvex(Polygon p)
    {
        return isConvex(p.x, p.y, p.n);
    }

    public static double crossProduct(double x0, double y0, double x1, double y1, 
            double x2, double y2)
    {
        return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
    }

    public static boolean isLeftTurn(double crossProduct)
    {
        return crossProduct < 0.0D;
    }

    public static boolean isRightTurn(double crossProduct)
    {
        return crossProduct > 0.0D;
    }

    public static boolean isColinear(double crossProduct)
    {
        return crossProduct == 0.0D;
    }

    public static int convexHull(double x[], double y[], int n)
    {
        if (n < 4)
            return n;
        int start = 0;
        for (int i = 0; i < n; i++)
            if (y[i] < y[start] || y[i] == y[start] && x[i] < x[start])
                start = i;

        double startX = x[start];
        double startY = y[start];
        insert(start, n - 1, x);
        insert(start, n - 1, y);
        for (int j = 1; j < n - 1;)
        {
            double key = angle(startX, startY, x[j], y[j]);
            int i;
            for (i = j - 1; i >= 0 && angle(startX, startY, x[i], y[i]) > key; i--);
            if (i > 0 && angle(startX, startY, x[i], y[i]) == key)
            {
                if (Point2D.distance(startX, startY, x[j], y[j]) > Point2D.distance(startX, startY, x[i], y[i]))
                {
                    overwrite(j, i, x, n);
                    overwrite(j, i, y, n);
                } else
                {
                    remove(j, x, n);
                    remove(j, y, n);
                }
                n--;
            } else
            {
                insert(j, i + 1, x);
                insert(j, i + 1, y);
                j++;
            }
        }

        int stack = n - 2;
        stack = push(x, y, stack);
        for (stack = push(x, y, stack); stack >= 0; stack = push(x, y, stack))
            while (isLeftTurn(crossProduct(x[stack + 2], y[stack + 2], x[stack + 1], y[stack + 1], x[0], y[0]))) 
                n = pop(x, y, stack, n);

        return n;
    }

    private static void insert(int src, int dest, double a[])
    {
        if (src < 0 || src >= a.length || dest < 0 || dest >= a.length)
            throw new ArrayIndexOutOfBoundsException("src=" + src + " dest= " + dest + " a.length=" + a.length);
        if (src == dest)
            return;
        double temp = a[src];
        if (src < dest)
            System.arraycopy(((Object) (a)), src + 1, ((Object) (a)), src, dest - src);
        else
            System.arraycopy(((Object) (a)), dest, ((Object) (a)), dest + 1, src - dest);
        a[dest] = temp;
    }

    private static int overwrite(int src, int dest, double a[], int n)
    {
        if (src < 0 || src >= a.length || dest < 0 || dest >= a.length || n < 1 || n < a.length)
            throw new ArrayIndexOutOfBoundsException("src=" + src + " dest= " + dest + " a.length=" + a.length + " n= " + n);
        if (src == dest)
        {
            return n;
        } else
        {
            a[dest] = a[src];
            System.arraycopy(((Object) (a)), src + 1, ((Object) (a)), src, n - src - 1);
            return n - 1;
        }
    }

    private static int remove(int i, double a[], int n)
    {
        if (n < 1 || n > a.length || i < 0 || i >= n)
            throw new ArrayIndexOutOfBoundsException(" i=" + i + " a.length= " + a.length + " n=" + n);
        if (i == n - 1)
        {
            return n - 1;
        } else
        {
            System.arraycopy(((Object) (a)), i + 1, ((Object) (a)), i, n - i - 1);
            return n - 1;
        }
    }

    private static int push(double x[], double y[], int stack)
    {
        if (stack < 0 || stack >= x.length || stack >= y.length)
        {
            throw new ArrayIndexOutOfBoundsException(" x.length=" + x.length + " y.length= " + y.length + " stack=" + stack);
        } else
        {
            insert(0, stack, x);
            insert(0, stack, y);
            return stack - 1;
        }
    }

    private static int pop(double x[], double y[], int stack, int n)
    {
        if (n < 1 || n > x.length || n > y.length || stack < 0 || stack >= n)
        {
            throw new ArrayIndexOutOfBoundsException(" x.length=" + x.length + " y.length= " + y.length + " stack=" + stack + " n=" + n);
        } else
        {
            remove(stack + 1, x, n);
            remove(stack + 1, y, n);
            return n - 1;
        }
    }

    private static double angle(double startX, double startY, double x, double y)
    {
        return Math.atan2(y - startY, x - startX);
    }
}
